package com.leetcode.algorithm.y19.m04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

/**
 * leetcode-cn.com
 * (done)3. 无重复字符的最长子串
 * (done)11. 盛最多水的容器
 * (done)15. 三数之和
 * (TODO)16. 最接近的三数之和
 * (done)18. 四数之和
 * @author: jie.deng
 * @time: 2019年4月17日 上午9:29:45
 */
public class MySolution0417 {
    
    /**
     * 3. 无重复字符的最长子串
     * 
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     * 
     * 示例 1:
     * 
     * 输入: "abcabcbb"
     * 输出: 3 
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * 示例 2:
     * 
     * 输入: "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * 示例 3:
     * 
     * 输入: "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Set<Character> set = new LinkedHashSet<Character>();
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (!set.add(cur)) {
                if (max < set.size()) {
                    max = set.size();
                }
                for (Iterator<Character> iterator = set.iterator(); iterator.hasNext();) {
                    Character ch = iterator.next();
                    if (ch == cur) {
                        iterator.remove();
                        break;
                    }
                    iterator.remove();
                }
                set.add(cur);
            }
        }
        if (max < set.size()) {
            max = set.size();
        }
        return max;
    }
    
    /**
     * 11. 盛最多水的容器
     * 
     * 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     * 
     * 说明：你不能倾斜容器，且 n 的值至少为 2。
     * 
     * 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
     * 
     * 示例:
     * 
     * 输入: [1,8,6,2,5,4,8,3,7]
     * 输出: 49
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        if (height == null || height.length == 1) {
            return 0;
        }
        int len = height.length;
        int maxArea = 0;
        int left = 0;
        for (; left < len - 1; left++) {
            int right = left + 1;
            for (; right < len; right++) {
                maxArea = Math.max((right - left) * Math.min(height[left], height[right]), maxArea);
            }
        }
        return maxArea;
    }
    
    /**
     * 15. 三数之和
     * 
     * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
     * 
     * 注意：答案中不可以包含重复的三元组。
     * 
     * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
     * 
     * 满足要求的三元组集合为：
     * [
     *   [-1, 0, 1],
     *   [-1, -1, 2]
     * ]
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        // 实现思路
        // 1.将数组排序 
        // 2.定义三个指针，i，j，k。遍历i，那么这个问题就可以转化为在i之后的数组中寻找nums[j]+nums[k]=-nums[i]这个问题，也就将三数之和问题转变为二数之和
        int len = nums.length;
        List<List<Integer>> list = new ArrayList<List<Integer>>(); // 返回值
        Arrays.sort(nums);
        for (int idx1 = 0; idx1 <= len - 3; idx1++) { // 第一个数的取值范围[0,len-3]
            int num1 = nums[idx1];
            if (num1 > 0) {
                break;
            }
            if (idx1 >= 1 && num1 == nums[idx1 - 1]) {
                continue;
            }
            int target = -num1;
            int left = idx1 + 1;
            int right = len - 1;
            while (left < right && left >= idx1 + 1 && right <= len - 1) {
                if (nums[left] > target) {
                    break;
                }
                if (nums[right] + nums[right - 1] < target) {
                    break;
                }
                if (nums[left] + nums[right] == target) {
                    list.add(Arrays.asList(num1, nums[left], nums[right]));
                    while (++left < right && nums[left] == nums[left - 1]);
                } else if (nums[left] + nums[right] > target) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return list;
    }
    
    /**
     * 16. 最接近的三数之和
     * 
     * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
     * 
     * 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
     * 
     * 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        return target;
    }
    
    /**
     * 18. 四数之和
     * 
     * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
     * 
     * 注意：
     * 
     * 答案中不可以包含重复的四元组。
     * 
     * 示例：
     * 
     * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
     * 
     * 满足要求的四元组集合为：
     * [
     *   [-1,  0, 0, 1],
     *   [-2, -1, 1, 2],
     *   [-2,  0, 0, 2]
     * ]
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int len = nums.length;
        List<List<Integer>> list = new ArrayList<List<Integer>>(); // 返回值
        if (len < 4) {
            return list;
        }
        Arrays.sort(nums);
        for (int idx1 = 0; idx1 <= len - 4; idx1++) { // 第一个数的取值范围[0,len-4]
            int num1 = nums[idx1];
            if (num1 + nums[idx1 + 1] + nums[idx1 + 2] + nums[idx1 + 3] > target) {
                break;
            }
            if (num1 + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) {
                continue;
            }
            if (idx1 >= 1 && num1 == nums[idx1 - 1]) {
                continue;
            }
            for (int idx2 = idx1 + 1; idx2 <= len - 3; idx2++) { // 第二个数的取值范围[0,len-3]
                int num2 = nums[idx2];
                if (num1 + num2 + nums[idx2 + 1] + nums[idx2 + 2] > target) {
                    break;
                }
                if (num1 + num2 + nums[len - 2] + nums[len - 1] < target) {
                    continue;
                }                
                if (idx2 > idx1 + 1 && num2 == nums[idx2 - 1]) {
                    continue;
                }
                int other = target - num1 - num2;
                int left = idx2 + 1;
                int right = len - 1;
                while (left < right && left >= idx2 + 1 && right <= len - 1) {
                    if (nums[right] + nums[right - 1] < other) {
                        break;
                    }
                    if (nums[left] + nums[right] == other) {
                        list.add(Arrays.asList(num1, num2, nums[left], nums[right]));
                        while (++left < right && nums[left] == nums[left - 1]);
                    } else if (nums[left] + nums[right] > other) {
                        right--;
                    } else {
                        left++;
                    }
                }
            }
        }
        return list;
    }
}
